﻿#define _CRT_SECURE_NO_WARNINGS
#include "BinarySearchTree.h"
#include<iostream>
#include<vector>
#include<list>
#include<string>

using namespace std;



//⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:
//• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值
//• 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值
//• 它的左右⼦树也分别为⼆叉搜索树
//• ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，后续我
//们学习map / set / multimap / multiset系列容器底层就是⼆叉搜索树，其中map / set不⽀持插⼊相等
//值，multimap / multiset⽀持插⼊相等值



//int main()
//{
//	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//	key::BSTree<int> b;
//	for (auto e : a)
//	{
//		b.Insert(e);
//	}
//
//	b.InOrder();
//	b.Erase(8);
//	b.InOrder();
//	return 0;
//}

//
//int main()
//{
//	key_value_teacher::BSTree<string, string> dict;
//	//BSTree<string, string> copy = dict;
//	dict.Insert("left", "左边");
//	dict.Insert("right", "右边");
//	dict.Insert("insert", "插⼊");
//	dict.Insert("string", "字符串");
//
//	string str;
//	while (cin >> str)
//	{
//		auto ret = dict.Find(str);
//		if (ret)
//		{
//
//			cout << "->"<< ret->_value << endl;
//		}
//		else
//		{
//			cout << "⽆此单词，请重新输⼊" << endl;
//		}
//	}
//	return 0;
//}


int main()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", 
		"西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	//key_value_mine::BSTree<string, int> countTree;
	key_value_teacher::BSTree<string, int> countTree;
	for (const auto& str : arr)
	{
		// 先查找⽔果在不在搜索树中 
		// 1、不在，说明⽔果第⼀次出现，则插⼊<⽔果, 1> 
		// 2、在，则查找到的结点中⽔果对应的次数++ 
		//BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == NULL)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.InOrder();
	return 0;
}

